#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@his-pc>
#
# Distributed under terms of the MIT license.

"""

"""

class LinkChain:
    def __init__(self, size_list):
        self.len = len(size_list)
        print('len is %s' % self.len)
        self.size_list = size_list

        row = [0] * self.len
        self.value_mat = [list(row) for i in range(self.len)]
        self.sep_mat   = [list(row) for i in range(self.len)]
        self.s = ""
        self.calc()

    def calc(self):
        # 跨度从1到len: range(1, len-1)
        len = self.len
        for span in range(1, len):      # 子链长度
            for begin in range(len - span):
                left, right = begin, begin+span
                cnt, sep = self.min_range(left, right)
                self.value_mat[left][right] = cnt
                self.sep_mat[left][right] = sep

    def min_range(self, left, right):
        # return min([self.calc_cnt(left, mid, right)for mid in range(left, right)])
        min = 99999
        sep = 0
        for mid in range(left, right):
            cnt = self.calc_cnt(left, mid, right)
            if cnt < min:
                # print(left, right)
                min = cnt
                sep = mid
        return min, sep

    def calc_cnt(self, left, mid, right):
        return self.value_mat[left][mid] \
               + self.value_mat[mid+1][right] \
                + self._matrix_mul_cnt(left, mid, right)

    def _matrix_mul_cnt(self, l, m, r):
        le, me, re = self.size_list[l], self.size_list[m], self.size_list[r]
        return le[0] * me[1] * re[1]

    def __str__(self):
        # return str(self.value_mat) + "\n" + str(self.sep_mat)

        # =================== 打印括号method1  =====================
        self.parenth_list = [[0, 0] for i in range(self.len)]
        self._parenth_method1(0, self.len-1)

        s = ""
        for i in range(self.len):
            e = self.parenth_list[i][0] * "(" +  "A" + str(i) +  self.parenth_list[i][1] * ")"
            s += e
        # return s

        # =================== 打印括号method2  =====================
        self._parenth_method2(0, self.len-1)
        return self.s + "\n" + " " + s

    def _parenth_method1(self, left, right):
        # 计算打印括号的位置
        LEFT = 0
        RIGHT = 1
        mid = self.sep_mat[left][right]
        if mid - left >= 1:
            self.parenth_list[left][LEFT] += 1
            self.parenth_list[mid][RIGHT] += 1
        if right - mid > 1:
            self.parenth_list[mid+1][LEFT] += 1
            self.parenth_list[right][RIGHT] += 1

        if mid - left >= 2:
            self._parenth_method1(left, mid)
        if right - mid >= 3:
            self._parenth_method1(mid+1, right)

    def _parenth_method2(self, left, right):
        # 计算打印括号的位置
        if left == right:
            # self.s.append("A%s" % left)
            self.s += "A%s" % left
            return

        # 这里 += 也可以直接print, 立马打印出来
        self.s += "("

        mid = self.sep_mat[left][right]
        self._parenth_method2(left, mid)
        self._parenth_method2(mid+1, right)

        self.s += ")"


def test():
    size_list = [(3, 4), (4, 9), (9,6), (6, 8), (8, 3), (3, 9)]
    # size_list = [(5, 4), (4, 6), (6,2), (2, 7)]
    m = LinkChain(size_list)
    print(m)


def main():
    print("start main")
    test()

if __name__ == "__main__":
    main()
